The present invention relates to a method for extracting the precise perimeter of buildings from down-looking terrain images without significant manual operations.
There are many features extraction techniques in the computer vision and image processing literature that could be applied to building perimeters. These techniques are collectively called object matching and can be summarized as four basic approaches:
1. Linking line segments. This is a bottom-up approach that extracts low level features, such as lines, and attempts to combine the lines to construct complex objects. The disadvantage is that the low level extraction is very susceptible to image noise and scene variation resulting in both missing important lines and including extraneous lines. Unlike the process of the present invention, low level extraction does not consider global constraints, such as the impact of building size, on including or excluding a line as a side. There are too many possible line segment combinations to consider. An example of this bottom-up approach is the Rectilinear Line Grouping System, University of Massachusetts, Amherst as reported in IEEE Computer, Dec. 1989, p. 28. The resulting building perimeters consist of unconnected line segments in which many walls are missing. Another disadvantage is speed. Extracting these low level feature for the entire image is computational expensive (proportional to N*M, the product of the image's dimensions) making the process too slow for many real-world applications.
2. Library of object models. This approach requires matching the image against a library of stored building perimeter shapes. State-of-the-art library matching approaches generally allow for variation in orientation and scale but not shape. This approach is appropriate when there is a finite number of objects that must be recognized such as letters of the alphabet. If a shape is not included in the library, the image cannot be matched. Thus, this approach will not accommodate generalized rectilinear buildings since the number of possible rectilinear shapes is infinite. Also, alphabet character recognition systems only classify objects, e.g., this is an "A," but not to determine their precise perimeters.
3. Parameterized object models. The size, shape and location of the matching model is controlled by the numerical values of parameters. An example of this approach is finding circle shapes in medical X-ray images as cited in Ballard and Brown, Computer Vision, 1982, Prentice Hall, p. 126. There were two parameters: center location and radius. This approach works only with relatively simple geometric shapes.
4. Segmented object models. Rather than trying to match complete objects, this approach attempts to match a relatively small number of generic object components. One such system looks for right angle corners and straight line segments by matching generic corner and straight line templates. These templates have a fixed scale so that only a small range of building sizes can be matched. The corners of larger scale buildings or noisy building images would appear to be rounded contours and would not be recognized as corners.
A generalized description of curve, or contour, following is given by Azriel Rosenfeld, Digital Image Processing, 2nd Ed., v. 2, Academic Press, 1982, pp. 130-138; chapter 11 is a survey of representations of image features, such as connectedness, size and shape. Representation of the traversal of an arbitrary digitized plane curve by chain codes was given by Herbert Freeman, IRE Transactions, EC 10 (1961) pp. 260-268. An alternative encoding for chain codes was given by Kenneth C. Knowlton, Proc. Spring Joint Computer Conference, 1964, pp 67-87. Efficient encoding of pixel neighborhood patterns for use in a contour follower was give by Irwin Sobel, Computer Graphics and Image Processing, v. 8, 1978, pp. 127-135. However, none of these sources mention the stopping condition, multiply-connected pixels, or use of multiple image data sets comprising the present invention.